class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        if (n==0) return vector<vector<int> >();
        vector<vector<int> > ret(n, vector<int>(n,-1));
        const int way[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
        int k=0, x=0, y=-1;
        for (int i=1;i<=n*n;i++)
            while (true) {
                int nx=x+way[k][0], ny=y+way[k][1];
                if (0<=nx && nx<n && 0<=ny && ny<n && ret[nx][ny]==-1) {
                    ret[nx][ny]=i;
                    x=nx;
                    y=ny;
                    break;
                } else k=(k+1)%4;
            }
        return ret;
    }
};
